package j2024.j202407;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class j0711 {
    //200
    int[] fx = new int[]{0,0,-1,1};
    int[] fy = new int[]{1,-1,0,0};
    boolean[][] vis = new boolean[301][301];
    int xlen,ylen;

    public int numIslands(char[][] grid) {
        int count = 0;
        xlen = grid.length;
        ylen = grid[0].length;
        for (int i = 0; i < xlen; i++) {
            for (int j = 0; j < ylen; j++) {
                if(grid[i][j] == '1' && !vis[i][j]){
                    count++;
                    BFS(grid,i,j);
                }
            }
        }
        return count;
    }

    public void BFS(char[][] grid,int i,int j){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        while(!q.isEmpty()){
            int[] a = q.poll();
            int c = a[0],d = a[1];
            for (int k = 0; k < 4; k++) {
                int x = c+fx[k];
                int y = d+fy[k];
                if(x>=0 && x<xlen && y>=0 && y<ylen && grid[x][y]=='1' && !vis[x][y]){
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }

    //695
    public int maxAreaOfIsland(int[][] grid) {
        xlen = grid.length;
        ylen = grid[0].length;
        int maxA = 0;
        for (int i = 0; i < xlen; i++) {
            for (int j = 0; j < ylen; j++) {
                if(grid[i][j]==1 && !vis[i][j]){
                    maxA = Math.max(maxA,bfs(grid,i,j));
                }
            }
        }
        return maxA;
    }

    public int bfs(int[][] grid,int i,int j){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        vis[i][j] = true;
        int area = 1;
        while(!q.isEmpty()){
            int[] r = q.poll();
            int a = r[0],b = r[1];
            for (int k = 0; k < 4; k++) {
                int x = a + fx[k],y = b + fy[k];
                if(x>=0 && x<xlen && y>=0 && y<ylen && grid[x][y]==1 && !vis[x][y]){
                    area++;
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
        return area;
    }


    public void solve(char[][] board) {
        xlen = board.length;
        ylen = board[0].length;
        //将边界上为‘O'的部分改成“-”
        for (int i = 0; i < xlen; i++) {
            if(board[i][0]=='O'){
                Bfs(board,i,0);
            }
            if(board[i][ylen-1]=='O'){
                Bfs(board,i,ylen-1);
            }
        }
        for (int i = 0; i < ylen; i++) {
            if(board[0][i]=='O'){
                Bfs(board,0,i);
            }
            if(board[xlen-1][i]=='O'){
                Bfs(board,xlen-1,i);
            }
        }
        //还原
        for (int i = 0; i < xlen; i++) {
            for (int j = 0; j < ylen; j++) {
                if(board[i][j]=='O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == '-'){
                    board[i][j]='O';
                }
            }
        }
    }
    public void Bfs(char[][] board,int i,int j){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        board[i][j] = '-';
        while(!q.isEmpty()){
            int[] r = q.poll();
            int a = r[0],b = r[1];
            for (int k = 0; k < 4; k++) {
                int x = a+fx[k];
                int y = b+fy[k];
                if(x>=0 && x<xlen && y>=0 && y<ylen && board[x][y]=='O'){
                    q.add(new int[]{x,y});
                    board[x][y] = '-';
                }
            }
        }
    }
    Stack<Integer> stack = new Stack<>();

}
